/*
* 贪心算法定义：只考虑眼前利益，不考虑全局，只求长久，只做当前最有利的事情，所以几乎不可能在一个计算量大的业务场景下得到一个最好的结果，
*            只求最快不求最好
*
* 无重叠区域：给定一个区间，该区间是一个二维数组的形式，移除该区间里重叠的项，使得该区间剩余项都不重叠
* eg:
*   [[1,2],[2,3],[3,4],[2,4]] 其中[2,4]就包含了[2,3]和[3,4] 所以需要删除这里重叠的区域 贪心算法不一定会算出最优解（删除一个[2,4]）
*
* 思路:
*   1.判断区域重叠的标准是什么？
*       给定任意两个区间[x1,y1],[x2,y2]（注意：这两个区间并未指明谁大谁小，所以需要分情况）
*       核心:不重叠的标准是什么？
*   2.判断x1和x2谁大谁小，假如x1 < x2，我们对数组进行排序，将区间左端小的数组排前面[x1,y1] [x2,y2]
*   3.此时x1是小于x2的，我们只需要判断y1与x2不相交则说明两者不重叠（即y1 <= x2）
*
* */

function noOverlappingRegion(array){ //接收一个数组
    let regionNum = array.length //子区间个数
    if(!regionNum){ //如果数组内都没有子区间，那根本不会有重叠区域
        return 0
    }

    //先进行排序，排完序才能进行比较
    array.sort((a,b) => a[0] - b[0]) //a，b分别代表两个区域子数组a[0]就是 x1，b[0]就是 x2
    console.log(array) //看看排序之后的数组情况

    let currentRegionIndex = 1 //当前区间索引
    let preRegionIndex = 0 //上一个区间索引
    let noOverlappingRegionNum = 0 //不重叠区间个数

    while(currentRegionIndex < regionNum){ //当我们还没有遍历完传入的总数组时，就一直循环遍历判断
        if(array[preRegionIndex][1] <= array[currentRegionIndex][0]){ //如果当前面区间的最大值小于等于后面区间的最小值时，说明不重复
            preRegionIndex = currentRegionIndex //就接着比较下一个区间（将当前区间定义为上一个区间，与接下来的区间比较）
            noOverlappingRegionNum++ //并且将不重叠区间加一
        }

        //否则不管重不重叠都遍历完了当前的区间，所以当前区间索引要自增
        currentRegionIndex++
    }

    //遍历完成之后，将总个数 - 无重叠区域个数 = 需要被删除的重叠区域个数
    return regionNum - noOverlappingRegionNum
}

noOverlappingRegion([[1,2],[2,3],[3,4],[2,4]]) //不求最好只求最快 39分14秒

//动态规划版本求无重叠区域，就能求出最优解（状态转义方程 边界 最优子结构）
function noOverlappingRegionPlus(array){ //接收一个数组
    let regionNum = array.length //子区间个数
    if(!regionNum){ //如果数组内都没有子区间，那根本不会有重叠区域
        return 0
    }

    //先进行排序，排完序才能进行比较
    array.sort((a,b) => a[0] - b[0]) //a，b分别代表两个区域子数组a[0]就是x1，b[0]就是x2
    console.log(array) //看看排序之后的数组情况

    //dp[i] 表示在二维数组里面从0到i个子区间里面的最长无重叠区域
    let dp = [] //定义一个数组，表示对应几个子数组情况下有几个最大不重叠区域
    dp[0] = 1 //（最优子结构）当二维数组里面只有一个子区间，那不就是一个无重叠区域
    for(let currentRegionIndex = 1; currentRegionIndex < regionNum; currentRegionIndex++){
        //解释一下为何currentRegionIndex = 1，currentRegionIndex代表dp数组中的下标，上面dp[0]已经存在了，所以从dp[1]开始
        //用dp[1]项子区间和dp[0]项子区间比较是否重叠

        let maxNoOverlappingRegionNum = 1 //默认最大无重叠区域为1，因为无论怎么样总有一个不重叠（100个有100个重叠，那不就是一个不重叠）
        //let currentStart = array[currentRegionIndex][0]
        let [currentStart] = array[currentRegionIndex] //这一行就是上一行的优雅写法，使用解构赋值，表示当前遍到的子区间的最小值（开始端点）

        for(let preRegionIndex = 0; preRegionIndex < currentRegionIndex; preRegionIndex++){ //preRegionIndex表示前面的子区间
            let [preStart,preEnd] = array[preRegionIndex] //表示前一个子区间的最小值（开始端点）和最大值（结束端点）
            if(preEnd <= currentStart){ //判断前区间数组的结束端点是否 <= 当前区间数组的开始端点
                maxNoOverlappingRegionNum = Math.max(maxNoOverlappingRegionNum,dp[preRegionIndex] + 1)
                //最大不重叠子区间个数 = （之前最大不重叠子区间个数）或者（之前最大不重叠子区间个数加上当前这1个不重叠子区间）二者选最大的
            }
        }
        dp[currentRegionIndex] = maxNoOverlappingRegionNum //更新当前子数组情况下对应最大不重叠子区间个数
        console.log(`dp[currentRegionIndex]是${dp[currentRegionIndex]}`)
        console.log(`dp是${dp}`)
    }
    //return regionNum - Math.max.apply(null,dp)
    return regionNum - Math.max(...dp) //下面这行是es6写法
}

noOverlappingRegionPlus([[1,2],[2,3],[3,4],[2,4]]) //55分57秒